# merge sort
def merge_sorted_list(list1,list2):
    result=[0]*(len(list1)+len(list2))
    id,id1,id2=0,0,0
    while id1 < len(list1) and id2 < len(list2):
        while id1 < len(list1) and id2 < len(list2) and list1[id1] <= list2[id2]:
            result[id]=list1[id1]
            id+=1
            id1+=1
        while id1 < len(list1) and id2 < len(list2) and list2[id2] < list1[id1]:
            result[id]=list2[id2]
            id+=1
            id2+=1
    if id1 != len(list1):
        result[id:]=list1[id1:]
    if id2 != len(list2):
        result[id:]=list2[id2:]
    return result
def merge_sort(array):
    if len(array) == 1:
        return array
    if len(array) == 2:
        if array[0] > array[1]:
            array[0],array[1]=array[1],array[0]
        return array
    half=len(array)//2
    array1=merge_sort(array[:half])
    array2=merge_sort(array[half:])
    return merge_sorted_list(array1,array2)

# large multiplier multiplication
def bigDataMutiple(s1,s2):
    if not s1 or not s2:
        return '0'
    elif len(s1) == 1 and len(s2) == 1:
        return str(int(s1)*int(s2))
    l1=len(s1)//2
    l2=len(s2)//2
    a=s1[:l1]
    b=s1[l1:]
    c=s2[:l2]
    d=s2[l2:]
    mi=len(b)
    ni=len(d)
    x1=bigDataMutiple(a,c)+'0'*(mi+ni)
    x2=bigDataMutiple(a,d)+'0'*mi
    x3=bigDataMutiple(b,c)+'0'*ni
    x4=bigDataMutiple(b,d)
    max_len=max(len(x1),len(x2),len(x3),len(x4))
    x1+='0'*(max_len-len(x1))
    x2+='0'*(max_len-len(x2))
    x3+='0'*(max_len-len(x3))
    x4+='0'*(max_len-len(x4))
    result=''
    c=0
    for i in range(max_len-1,-1,-1):
        s=int(x1[i])+int(x2[i])+int(x3[i])+int(x4[i])+c
        result+=str(s%10)
        c=s//10
    if c>0:
        result+=str(c)
    k=0
    while result and k < len(result) and result[k] == '0':
        k+=1
    return result[k:]

# find max sum subarray
def maxSubArray(array):
    def divide(array,left,right):
        if left == right:
            return array[left]
        mid=(left+right)//2
        leftSum=divide(array,left,mid)
        rightSum=divide(array,mid+1,right)
        leftVal=0
        leftMidSum=array[mid]-1
        for i in range(mid,left-1,-1):
            leftVal+=array[i]
            leftMidSum=max(leftVal,leftMidSum)
        rightVal=0
        rightMidSum=array[mid+1]-1
        for i in range(mid+1,right+1):
            rightVal+=array[i]
            rightMidSum=max(rightVal,rightMidSum)
        return max(max(leftSum,rightSum),leftMidSum+rightMidSum)
    return divide(array,0,len(array)-1)

# minimum k numbers
def find_min(array,k):
    array.sort()
    return array[:k]

def smallestK(array,k):
    def divide(array,left,right,k):
        if not k:
            return []
        if (right-left+1) <= k:
            return array[left:right+1]
        mid=(left+right)//2
        array_left_k=divide(array,left,mid,k)
        array_right_k=divide(array,mid+1,right,k)
        array_k=[]
        for i in range(len(array_left_k)):
            array_k.append(array_left_k[i])
        array_k+=array_right_k
        array_k.sort()
        return array_k[:k]
    return divide(array,0,len(array)-1,k)

# beautiful array
def beautifulArray(N):
    memo={1:[1]}
    def f(N):
        if N not in memo:
            odds=f((N+1)//2)
            evens=f(N//2)
            memo[N]=[ 2*x-1 for x in odds ]+[ 2*x for x in evens ]
        return memo[N]
    return f(N)
